package com.cn.algorithm01;


import java.util.Random;

/***
 * @author: hels
 * @description:  快速排序
 * @date: 2022-9-14 19:52
 **/
public class Code27_PartitionAndQuickSort {
    // 无序数组
    static int[] arr = new int[17];
    public static void setArr() {
        Random random = new Random();
        for (int i = 0; i < 17; i++) {
            arr[i] = random.nextInt(20);
            System.out.print(arr[i] + " ");
        }
    }
    public static void main(String[] args) {
        setArr();
        // 分区排序
         //sort1Partition();
        // sort1();

        // 快速排序
        quick(arr, 0, arr.length-1);


        System.out.println("sort over...");
        for (int num: arr) {
            System.out.print(num + " ");
        }

    }

    // quick 排序
    public static void quick(int[] arr, int L, int R) {
        if (arr == null || arr.length < 2) {
            return;
        }

        process(arr, L, R);
    }

    public static void process(int[] arr, int L, int R) {
        if (L >= R ) {
            return;
        }

        int[] eqlArr = partition(arr, L, R);
        // eqlArr[0]  小于区的右边界
        // eqlArr[1]  大于区的左边界
        process(arr, L, eqlArr[0]);
        process(arr, eqlArr[1], R);
    }

    // 通过快速排序一个数组
    public static int[] partition(int[] arr, int L, int R) {
        int p1 = L, p2 = L-1, p3 = R + 1;
        int tail = arr[R];
        while (p1  < p3) {
            if (arr[p1] < tail) {
                swap(arr, p1++ , ++p2);
            } else if (arr[p1] > tail) {
                swap(arr, p1 , --p3);
            } else {
                p1++;
            }
        }
        return new int[]{p2, p3};
    }

    // sort2: 以最后一位数为基准，小于的放左边，大于的放右边，相同的放中间
    //origin: 5 3 4 6 2 4
    //sorted: 3 2 4 4 5 6
    // 测试ok
    public static void sort2Partition() {
        int len = arr.length;
        int p1 = 0, p2 = -1, p3 = len;
        int tail = arr[len - 1];
        System.out.println("start...");
        while (p1  < p3) {
            if (arr[p1] < tail) {
                swap(arr, p1++ , ++p2);
               /* int tmp = arr[p1];
                arr[p1] = arr[++p2];
                arr[p2] = tmp;
                p1++;*/
            } else if (arr[p1] > tail) {
                swap(arr, p1 , --p3);
               /* int tmp = arr[p1];
                arr[p1] = arr[--p3];
                arr[p3] = tmp;*/
            } else if (arr[p1] == tail) {
                swap(arr, p1++ , p2 + 1);
                /*int tmp = arr[p1];
                arr[p1] = arr[p2 + 1];
                arr[p2 + 1] = tmp;
                p1++;*/
            }

        }
        System.out.println("sort over...");
    }

    // sort1: 以最后一位数为基准，小于等于的放左边，大于的放右边，最后一位数放中间
    //origin: 5 3 4 6 2 4
    //sorted: 3 4 2 4 5 6
    // 测试ok
    public static void sort1Partition() {
        int p1 = 0, p2 = -1;
        int len = arr.length;
        int tail = arr[len - 1];
        System.out.println("start...");
        while (p1 < len) {
            if (arr[p1] <= tail) {
                swap(arr, p1++, ++p2);
              /*  int tmp = arr[p1];
                arr[p1] = arr[++p2];
                arr[p2] = tmp;*/
            } else {
                p1++;
            }
        }
        System.out.println("sort over...");
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
